Ja, wir haben uns das letzte Mal, sind wir so weit gekommen, dass wir die Suchbäume eingeführt haben.

Ich will da nochmal das letzte Beispiel, das ich am Ende gebracht habe, nochmal wiederholen.

Das Einfügen in einen Binären Suchbaum, also erinnern wir uns da dran, wir haben einen Baum und an

jeden Knoten ist ein Wert assoziiert und es gibt eine Ordnung auf diesen Werten, zum Beispiel

alphabetische Ordnung oder numerisch oder so. Und wenn ihr also so eine Ordnung habt und ihr sagt,

im linken Unterbaum sind immer Werte kleiner und im rechten Unterbaum immer Werte größer,

die sind geordnet, dann haben wir das letzte Mal gesehen, dann kann die Suche in so einem Baum

sehr viel effizienter geschehen, als wenn wir das in einer verketteten Liste machen und die Zahl

der Such- und Vergleichsschritte steigt mit der Höhe des Suchbaumes und nicht mit der Anzahl

der Elemente. Und vielleicht erinnern Sie sich in der Woche davor, da hatten wir eben auch uns

überlegt, wie viele Knoten in einem Baum der Höhe n sind. Das heißt, so ein Suchbaum ist

natürlich eine enorme Beschleunigung, er möchte eine enorme Beschleunigung. Wir haben geendet mit

dem Einfügen in einen binären Suchbaum und festgestellt, das Einfügen funktioniert nach

dem gleichen Prinzip wie das Suchen. Und wenn die Suche nach dem einzufügenden Element an einem

Knoten erfolglos ist, lässt man in diesem Knoten das neue Element verweisen und wie gesagt,

die Komplexität ist die gleiche wie die Suchoperation. Und jetzt baue ich mir mal so

einen Baum auf. Ich fange also an mit einem Element. Das nächste Element, naja, was passiert,

es ist kleiner, also wird es im linken Unterbaum aufgebaut. Das nächste Element ist kleiner als

der Knoten, die Wurzel, gehe ich links runter. Dann bei der 12 ist es größer, also wird es in

dem rechten Unterbaum von 12 aufgebaut. Und das mache ich jetzt schön weiter und dann habe

ich meinen Suchbaum schrittweise aufgebaut. Okay? Vorgehensweise beim Einfügen, klar? Schauen wir

uns den Code dafür an. Also wir haben eine Methode Einfügen, der geben wir einen Wert mit. In

dem Fall haben wir einen Suchbaum mit numerischen Werten, also ein integer wird übergeben. Wir

initialisieren den Knoten mit der Wurzel. Die Wurzel hat keinen Vaterknoten und wir erzeugen

einen neuen Knoten. Und dieser Knoten hat den Wert, den wir einfügen wollen. So, das passiert

hier oben. Jetzt müssen wir nachschauen, das ist der Sonderfallbehandlung. Ist denn der Baum leer?

Also wenn die Wurzel leer ist, dann wird die Wurzel einfach mit dem neu einzufügenden Wert

besetzt. Ansonsten müssen wir die Position in dem Baum suchen, indem wir den Baum nach unten durchgehen

und wir müssen an der gewünschten Stelle einfügen. Jetzt schauen wir uns die Position suchen an. Wir

wollen also, wir sagen, solange der Knoten nicht auf Null zeigt, jetzt wenn der Knotenwert gleich dem

einzufügenden Wert ist, dann ist er ja schon drin, dann werfen wir eine Exception. Ansonsten, dann

sind sie ungleich, dann sagen wir, der aktuelle Knoten ist jetzt der Vaterknoten und wir schauen

nach, ob der Wert, den wir einfügen wollen, kleiner ist, dann machen wir im linken Teilbaum

weiter und wenn er größer ist, im rechten Teilbaum. Und so lange laufen wir durch, bis wir an die

Stelle kommen. Also solange der Knoten nicht auf Null zeigt, gehen wir den Baum runter, bis wir an

eine Stelle kommen, wo wir einfügen können. Und das einfügen, das passiert jetzt so, dass wir sagen,

wenn der Wert größer der Wert des Vaterknotens ist, dann wird der rechte Unterbaum, also dieser

Knoten hat er jetzt keine Nachfolger mehr, dann wird der rechte Unterbaum auf den neuen Knoten

gesetzt und ansonsten der linke. Ist dieser Ausschnitt aus dem Programm zusammen mit der

Grafik von vorhin klar? Okay. Beim Löschen ist ein bisschen komplizierter, aber auch nicht viel.

Wenn der zu löschende Knoten keinen Nachfolger hat, das ist der Trivialfall, löschen wir ihn

einfach. Wenn der Knoten einen Nachfolger hat, das ist auch noch relativ einfach, dann wird einfach

der Nachfolger an die Stelle gesetzt. Und wenn er zwei Nachfolger hat, dann wird es ein bisschen

komplizierter, aber auch nicht arg, dann wird der zu löschende Knoten durch den am weitesten rechts

liegenden Knoten im linken Teilbaum oder den am weitesten links liegenden Knoten im rechten

Teilbaum ersetzt. Und dieser Knoten muss dann aus dem entsprechenden Teilbaum entfernt werden. Und

das schauen wir uns jetzt gleich mal an, an einem Beispiel. Also wir haben hier einen Baum und bei

dem wollen wir den Knoten 9 löschen. Der Knoten 9, der hat zwei Unterbäume, also müssen wir jetzt

die 9 löschen und durch den am weitesten rechts positionierten Teilbaum im linken Unterbaum ersetzen

oder durch den am weitesten links liegenden Teilbaum im rechten Unterbaum. Warum? Naja, das ist klar.